package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         109,
		Discription: "将升序链表转化为二叉搜索树",
		Level:       2,
		Labels: map[string]int{
			"递归":   1,
			"二叉树":  1,
			"双重指针": 1,
		},
	})
}

func SortedListToBST(head *ds.ListNode) *ds.TreeNode {
	if head == nil {
		return nil
	}

	length := 0
	temp := head
	for temp != nil {
		length++
		temp = temp.Next
	}

	//用双重指针的目的：在构造其它子树时，所有调用栈方法中的链表中的startNode会跟着移动（由于是通过TreeNode指针的指针去访问TreeNode的指针的，所以对TreeNode指针进行移动时，通过TreeNode指针的指针可以观察到移动)
	//ListNode：中序遍历开始的节点
	//size：树中节点的数量
	var build func(**ds.ListNode, int) *ds.TreeNode
	build = func(startNode **ds.ListNode, size int) *ds.TreeNode {
		if size <= 0 {
			return nil
		}

		root := &ds.TreeNode{}
		root.Left = build(startNode, size/2)
		//此时startNode指向的是root的位置
		root.Val = (*startNode).Val
		//每用一个值head往前挪一位
		*startNode = (*startNode).Next
		//注意size-size/2-1，减掉本身root的位置
		root.Right = build(startNode, size-size/2-1)
		return root
	}

	return build(&head, length)
}
